package list

import (
	"math"
	"math/rand"
)

/*
	跳跃表的节点
*/
type skipListNode struct {
	// 存储的数据
	data interface{}
	// 跳跃表排序的分数，也可以理解成索引的唯一键
	score int
	//当前层下一个节点
	next *skipListNode
	//连接下一层的节点
	down *skipListNode
	// 当前层的level
	level int
}

/*
	跳跃表的结构，可以用作纯内存的log(n)效率的索引结构。
	和hashtable相比劣势会消耗更多的内存构建索引，查询效率不是O(1)。优势是支持按照分数以log(n)的效率进行范围检索。
	和树结构相比插入删除操作简单效率高，不需要处理平衡问题。范围查询和排名查询不需要额外遍历操作，效率会高。
	head->      3->   tail
	  |			|	   |
	head->   2->3->4->tail
	  |		 |	|  |   |
	head->1->2->3->4->tail
*/
type SkipList struct {
	// 每层的头部节点
	headSkipNodes *LinkedList
	// 每层的尾部节点
	tailSkipNodes *LinkedList
	// 当前层数
	curLevel int
	// 生成随机数
	random *rand.Rand
	// 跳跃表中元素个数
	size int64
}

/*
	获取随机向跳跃表中添加元素的层数
*/
func (skipList SkipList) getRandomLevel() int {
	level := 0
	// 一半的概率增加一层
	for skipList.random.Intn(2) > 1 {
		level++
	}
	return level
}

/*
	扩充层数
*/
func (skipList *SkipList) addLevel(addLevelNum int) {
	getLowHead, _ := skipList.headSkipNodes.GetFirst()
	getLowTail, _ := skipList.tailSkipNodes.GetFirst()

	lowHead := getLowHead.(*skipListNode)
	lowTail := getLowTail.(*skipListNode)

	for i := 0; i < addLevelNum; i++ {
		lowHead, lowTail = skipList.addHighHeadTailNode(lowHead, lowTail, false)
	}

	skipList.curLevel = skipList.curLevel + addLevelNum
}

/*
	向跳跃表重追加更高level的max和min节点，并返回最高level的min和max节点
*/
func (skipList *SkipList) addHighHeadTailNode(lowHead *skipListNode, lowTail *skipListNode, zeroLevel bool) (*skipListNode, *skipListNode) {
	var highLevelHead *skipListNode
	var highLevelTail *skipListNode
	if zeroLevel {
		highLevelHead = &skipListNode{score: math.MinInt64, level: 0}
		highLevelTail = &skipListNode{score: math.MaxInt64, level: 0}
	} else {
		highLevelHead = &skipListNode{score: lowHead.score, level: lowHead.level + 1, down: lowHead}
		highLevelTail = &skipListNode{score: lowTail.score, level: lowTail.level + 1, down: lowTail}
	}

	highLevelHead.next = highLevelTail

	skipList.headSkipNodes.AddFirst(highLevelHead)
	skipList.tailSkipNodes.AddFirst(highLevelTail)
	return highLevelHead, highLevelTail
}

/*
	查找存在对应的最高层级的节点的前置节点
*/
func (skipList SkipList) findHighLevelPreNode(score int) (*skipListNode, bool) {
	// 目标值等于当前节点，直接返回数据
	getFirst, _ := skipList.headSkipNodes.GetFirst()
	curNode := getFirst.(*skipListNode)
	for curNode != nil && curNode.next != nil {
		if curNode.next.score == score {
			if curNode.next.next == nil {
				// 如果找到的是max节点，默认是认为没有，除非在max节点前还有max节点
				return nil, false
			} else {
				return curNode, true
			}
		} else if curNode.next.score > score {
			// 在当前索引和下一个索引之间，到下一层进行更细致的寻找
			curNode = curNode.down
		} else {
			// 不在当前层的这个区间，判断下一个区间
			curNode = curNode.next
		}
	}
	return nil, false
}

/*
	查找是否存在对应的最高层级的节点
*/
func (skipList SkipList) findHighLevelNode(score int) (*skipListNode, bool) {
	// 目标值等于当前节点，直接返回数据
	highLevelPreNode, find := skipList.findHighLevelPreNode(score)
	if find {
		highLevelNode := highLevelPreNode.next
		return highLevelNode, find
	}
	return nil, false
}

func (skipList SkipList) Find(score int) (interface{}, bool) {
	highLevelNode, find := skipList.findHighLevelNode(score)
	if find {
		for highLevelNode.down != nil {
			highLevelNode = highLevelNode.down
		}
		// 已经存在了的score 直接更新data就可以了
		return highLevelNode.data, find
	}
	return nil, false
}

/*
	向跳跃表中添加数据,需要注意的是数据只存储在level=0的节点上，有利于节省空间
*/
func (skipList *SkipList) Add(score int, data interface{}) {
	highLevelNode, find := skipList.findHighLevelNode(score)
	if find {
		for highLevelNode.down != nil {
			highLevelNode = highLevelNode.down
		}
		// 已经存在了的score 直接更新data就可以了
		highLevelNode.data = data
	} else {
		// 不存在的score才需要插入数据
		// 随机选定插入元素的层数
		level := skipList.getRandomLevel()

		if level > skipList.curLevel {
			// 先扩充层数
			skipList.addLevel(level - skipList.curLevel)
		}

		// 添加元素
		curNode := &skipListNode{score: score, level: level}
		// 获取插入最高层的headNode，从最高层到最低层每层都插入值
		getPreNode, _ := skipList.headSkipNodes.Get(skipList.curLevel - level)
		preNode := getPreNode.(*skipListNode)
		for i := level; i >= 0; i-- {
			// 使得preNode.score<score<=preNode.next.score
			for preNode.next.score < score {
				preNode = preNode.next
			}
			// 将新node插入该层
			curNode.next = preNode.next
			preNode.next = curNode

			if curNode.level > 0 {
				//创建下一层的节点
				downLevel := &skipListNode{score: score, level: curNode.level - 1}
				// 关联下一层的节点
				curNode.down = downLevel

				// 将下一层的节点放入到下一层合适的位置
				curNode = downLevel
				// preNode也寻找下一层的节点
				preNode = preNode.down
			} else {
				curNode.data = data
			}
		}
		skipList.size++
	}
}

/**
删除对应分数的所有数据
*/
func (skipList *SkipList) Remove(score int) {
	findHighLevelPreNode, ok := skipList.findHighLevelPreNode(score)
	if ok {
		// 找到的话，进行删除
		for true {
			next := findHighLevelPreNode.next
			findHighLevelPreNode.next = next.next
			// 断开删除节点和其他节点的连接
			next.next = nil
			next.down = nil

			// 删除下一层
			findHighLevelPreNode = findHighLevelPreNode.down

			if findHighLevelPreNode == nil {
				// 已经删除完最后一层了
				break
			}
			for findHighLevelPreNode.next.score != score {
				// 正常在最高层之下的每一层都会找到对应的值
				findHighLevelPreNode = findHighLevelPreNode.next
			}
		}
		skipList.size--
	}
}
